package leetcode;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-6-10
 * Time: 下午4:44
 * To change this template use File | Settings | File Templates.
 */

/**
 * 卡特兰数：
 * S0 = 1;
 * S1 = 1；
 * Sn = Sum(Si*Sn-i-1); i from 0 to n-1
 */
public class Unique_Binary_Search_Trees {
    public static int numTrees(int n) {
        if(n==0 || n==1){
            return 1;
        }
        else {
            int rst = 0;
            for(int i=0;i<n;i++){
                rst += numTrees(i)*numTrees(n-i-1);
            }
            return rst;
        }
    }
    public static void main(String[] args){
        System.out.println(numTrees(10));
    }
}
